{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d8c7332b-9a35-444e-82df-fcc6271afe2c",
   "metadata": {},
   "source": [
    "# 300. 最长递增子序列\n",
    "\n",
    "给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。\n",
    "\n",
    "子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。\n",
    "\n",
    " \n",
    "示例 1：\n",
    "\n",
    "> 输入：nums = [10,9,2,5,3,7,101,18]  \n",
    "> 输出：4  \n",
    "> 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。\n",
    "\n",
    "示例 2：\n",
    "\n",
    "> 输入：nums = [0,1,0,3,2,3]\n",
    "> 输出：4\n",
    "\n",
    "示例 3：\n",
    "\n",
    "> 输入：nums = [7,7,7,7,7,7,7]\n",
    "> 输出：1\n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "- 1 <= nums.length <= 2500  \n",
    "- $-10^4$ <= nums[i] <= $10^4$\n",
    " \n",
    "\n",
    "进阶：\n",
    "\n",
    "- 你能将算法的时间复杂度降低到 O(n log(n)) 吗?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3005029e-eb9e-4688-9347-904309ca1694",
   "metadata": {},
   "source": [
    "## 1、暴⼒递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "60d922e7-3bad-4629-a4a6-ab8698f8ac01",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lengthOfLIS(nums):\n",
    "    def dp(n):\n",
    "        # base case\n",
    "        if n == 0: return 1\n",
    "\n",
    "        res = 1\n",
    "        for i in range(n):\n",
    "            if nums[i] < nums[n]:\n",
    "                res = max(res, 1 + dp(i))\n",
    "        \n",
    "        return res\n",
    "\n",
    "    # lis_len[i] 表⽰以 nums[i] 这个数结尾的最⻓递增⼦序列的⻓度。\n",
    "    lis_len = [0]*len(nums)\n",
    "    for i in range(len(nums)):\n",
    "        lis_len[i] = dp(i)\n",
    "    return max(lis_len)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "41d919e7-f67e-4fa8-9cbe-05981bea01fe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "4\n",
      "1\n",
      "3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "print(lengthOfLIS([10,9,2,5,3,7,101,18]))\n",
    "print(lengthOfLIS([0,1,0,3,2,3]))\n",
    "print(lengthOfLIS([7,7,7,7,7,7,7]))\n",
    "print(lengthOfLIS([4,10,4,3,8,9]))\n",
    "print(lengthOfLIS([3,5,6,2,5,4,19,5,6,7,12]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "692729b9-0fee-4334-8676-e78ec32aa3da",
   "metadata": {},
   "source": [
    "## 2、带备忘录的递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "cbb0c9ca-e4b3-4b11-9cbc-e9dcd03d6786",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lengthOfLIS(nums):\n",
    "    # 备忘录\n",
    "    memo = dict()\n",
    "    \n",
    "    def dp(n):\n",
    "        # 查备忘录，避免重复计算\n",
    "        if n in memo: return memo[n]\n",
    "\n",
    "        # base case\n",
    "        if n == 0: return 1\n",
    "\n",
    "        res = 1\n",
    "        for i in range(n):\n",
    "            if nums[i] < nums[n]:\n",
    "                res = max(res, 1 + dp(i))\n",
    "\n",
    "        # 记⼊备忘录\n",
    "        memo[n] = res        \n",
    "        return res\n",
    "\n",
    "    # len[i] 表⽰以 nums[i] 这个数结尾的最⻓递增⼦序列的⻓度。\n",
    "    lis_len = [0]*len(nums)\n",
    "\n",
    "    for i in range(len(nums)):\n",
    "        lis_len[i] = dp(i)\n",
    "    return max(lis_len)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "8e7ed522-2b6e-40d2-9ce7-b10697d4001f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "4\n",
      "1\n",
      "3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "print(lengthOfLIS([10,9,2,5,3,7,101,18]))\n",
    "print(lengthOfLIS([0,1,0,3,2,3]))\n",
    "print(lengthOfLIS([7,7,7,7,7,7,7]))\n",
    "print(lengthOfLIS([4,10,4,3,8,9]))\n",
    "print(lengthOfLIS([3,5,6,2,5,4,19,5,6,7,12]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "348a26ad-53b2-4bb4-b1a5-12b1d8a7aaba",
   "metadata": {},
   "source": [
    "## 3、dp 数组的迭代解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "464b3b9d-e5e4-4b6d-8eeb-40439b574f3b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lengthOfLIS(nums):\n",
    "    # dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度\n",
    "    dp = [1]*len(nums)\n",
    "\n",
    "    for n in range(len(nums)):\n",
    "        for i in range(n):\n",
    "            if nums[i] < nums[n]:\n",
    "                dp[n] = max(dp[n], 1 + dp[i])\n",
    "\n",
    "    return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d48602cc-a474-4d38-9486-d7da36cad466",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "4\n",
      "1\n",
      "3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "print(lengthOfLIS([10,9,2,5,3,7,101,18]))\n",
    "print(lengthOfLIS([0,1,0,3,2,3]))\n",
    "print(lengthOfLIS([7,7,7,7,7,7,7]))\n",
    "print(lengthOfLIS([4,10,4,3,8,9]))\n",
    "print(lengthOfLIS([3,5,6,2,5,4,19,5,6,7,12]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d2eccf8-cfb7-41ea-a3b3-cef08a3b4460",
   "metadata": {},
   "source": [
    "## 4、回溯打印"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "6cd156bb-8c07-472e-884b-90bd7bd4958c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lengthOfLIS(nums):\n",
    "    # dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度\n",
    "    dp = [1] * len(nums)\n",
    "    # prev 数组用于记录前驱元素的位置\n",
    "    prev = [-1] * len(nums)\n",
    "\n",
    "    for n in range(len(nums)):\n",
    "        for i in range(n):\n",
    "            if nums[i] < nums[n] and dp[n] < 1 + dp[i]:\n",
    "                dp[n] = 1 + dp[i]\n",
    "                prev[n] = i\n",
    "\n",
    "    # 找到最长子序列的结束位置\n",
    "    max_len = max(dp)\n",
    "    end_index = dp.index(max_len)\n",
    "\n",
    "    # 回溯构建最长子序列\n",
    "    lst = []\n",
    "    while end_index != -1:\n",
    "        lst.append(nums[end_index])\n",
    "        end_index = prev[end_index]\n",
    "\n",
    "    # 反转列表得到正确的顺序\n",
    "    print(lst[::-1])\n",
    "\n",
    "    return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "aed0e5cc-dd00-44d2-a614-aa3824981332",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 5, 7, 101]\n",
      "4\n",
      "[0, 1, 2, 3]\n",
      "4\n",
      "[7]\n",
      "1\n",
      "[4, 8, 9]\n",
      "3\n",
      "[3, 4, 5, 6, 7, 12]\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "print(lengthOfLIS([10,9,2,5,3,7,101,18]))\n",
    "print(lengthOfLIS([0,1,0,3,2,3]))\n",
    "print(lengthOfLIS([7,7,7,7,7,7,7]))\n",
    "print(lengthOfLIS([4,10,4,3,8,9]))\n",
    "print(lengthOfLIS([3,5,6,2,5,4,19,5,6,7,12]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b450811-1a7a-478f-94c1-58e444a5460a",
   "metadata": {},
   "source": [
    "参考资料：\n",
    "- 《labuladong的算法小抄》：第⼀章、动态规划系列 动态规划设计：最⻓递增⼦序列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "869989c9-0dc6-46e7-8adb-236d8b67e286",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
